package jm.algorithm.dp;

/**
 * @Description 找零钱实现
 * @date 2022/5/22 15:30
 */
public class CoinChange {
    public static void main(String[] args) {
        int[] faces = {1, 5, 20, 25};
        System.out.println(new CoinChange().coins(41 ,faces));
    }

    /**
     * 暴力递归 - 自顶向下，有重叠子问题
     * @param money 要找的钱
     * @return
     */
    public int coins1(int money){
        // 当剩余找回金额小于当前硬币面额时，赋值最大值，让他选择另一个小的。
        if (money < 1) return Integer.MAX_VALUE;
        if (money == 25 || money == 20 || money == 5 || money == 1) return 1;
        int min1 = Math.min(coins1(money - 25), coins1(money - 20));
        int min2 = Math.min(coins1(money - 5), coins1(money - 1));
        return Math.min(min1, min2) + 1;
    }

    /**
     * 记忆化搜索，不存在重叠子问题
     * @param money
     * @return
     */
    public int coins2(int money){
        // 小于最小面额，不符合直接返回-1
        if (money < 1) return -1;

        // 存放计算过的结果：索引是找回金额值，对应值是硬币数量
        int[] dp = new int[money + 1];
        // 初始化面值
        int[] faces = {1, 5, 20, 25};
        for (int face : faces) {
            if (money < face) break;
            dp[face] = 1;
        }
        return coins2(money, dp);
    }

    public int coins2(int money,int[] dp){
        if (money < 1) return Integer.MAX_VALUE;
        if (dp[money] == 0){
            int min1 = Math.min(coins2(money - 25, dp), coins2(money - 20 ,dp));
            int min2 = Math.min(coins2(money - 5, dp), coins2(money - 1, dp));
            dp[money] = Math.min(min1, min2) + 1;
        }
        return dp[money] ;
    }

    /**
     * 自底向上递推
     * @param money 金额
     * @return
     */
    public int coins3(int money){
        if (money < 1)  return -1;
        // dp中存储每个金额所需要的硬币数量
        int[] dp = new int[money + 1];
        for (int i = 1; i <= money; i++) {
            // 首先，在进行初始化之前数组的所有值都为 0
            int min = dp[i -1];
            // 恰好等于面额时当前面额的索引在dp中一定不存在（为0）
            // 恰好可以初始化当前面额的硬币数为 1
            if (i >= 5) min = Math.min(dp[i - 5], min);
            if (i >= 20) min = Math.min(dp[i - 20], min);
            if (i >= 25) min = Math.min(dp[i - 25], min);
            dp[i] = min + 1;
        }
        return dp[money];
    }

    /**
     * 递推记录所选硬币
     * @param money
     * @return
     */
    public int coins4(int money){
        if (money < 1) return -1;
        int[] dp = new int[money + 1];
        // faces[i]存储凑够 i 分时最后选择的硬币的吗面值
        int[] faces = new int[dp.length];
        for (int i = 1; i <= money; i++) {
            int min = Integer.MAX_VALUE;
            if (i >= 1 && dp[i - 1] < min){
                min = dp[i - 1];
                faces[i] = 1;
            }
            if (i >= 5 && dp[i - 5] < min){
                min = dp[i - 5];
                faces[i] = 5;
            }if (i >= 20 && dp[i - 20] < min){
                min = dp[i - 20];
                faces[i] = 20;
            }
            if (i >= 25 && dp[i - 25] < min){
                min = dp[i - 25];
                faces[i] = 25;
            }
            dp[i] = min + 1;
        }
        System.out.println();
        print(faces,money);
        return dp[money];
    }

    public void print(int[] faces,int i){
        // 首先faces[i]的值是凑够 i 最后的一个硬币面值
        // n - faces[i] 就是剩下的所需要凑够的面值
        // 所以 faces[n - faces[i]] 就是剩下的面值中的最后一个硬币面值！
        while (i > 0){
            System.out.print(faces[i] + ",");
            i -= faces[i];
        }
        System.out.println();
    }


    /**
     * 通用
     * @param n 总面额
     * @param faces 可选面额
     * @return
     */
    public int coins(int n, int[] faces){
        if (n < 1 || faces == null || faces.length == 0) return -1;
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int face : faces) {
                // 如果
                if (i < face) continue;
                if (dp[i - face] < 0 || dp[i - face] >= min) continue;
                min = dp[i - face];
            }
            if (min == Integer.MAX_VALUE){
                dp[i] = -1;
            }else {
                dp[i] = min + 1;
            }
        }
        return dp[n];
    }

    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (amount < 1 || coins == null || coins.length == 0) return -1;
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            int min = Integer.MAX_VALUE;
            for (int face : coins) {
                // 如果
                if (i < face) continue;
                if (dp[i - face] < 0 || dp[i - face] >= min) continue;
                min = dp[i - face];
            }
            if (min == Integer.MAX_VALUE){
                dp[i] = -1;
            }else {
                dp[i] = min + 1;
            }
        }
        return dp[amount];
    }
}
